package leetcode.bit;

import java.util.Arrays;

// 不用任何算术运算，只用位运算实现加减乘除
// 代码实现中你找不到任何一个算术运算符
// 测试链接 : https://leetcode.cn/problems/divide-two-integers/
public class Code_BitOperationAddMinusMultiplyDivide {

    /**
     * 将进位加法拆分为无进位加法（异或运算） + 进位信息（&与运算右移）
     *
     * @param a
     * @param b
     * @return
     */
    public int add(int a, int b) {
        // 如果b == 0 返回a
        int ans = a;
        while (b != 0) {
            ans = a ^ b;
            b = (a & b) << 1;
            a = ans;
        }
        return ans;
    }

    public int minus(int a, int b) {
        // a - b = a + (-b)
        // -b = add(~b, 1)
        return add(a, add(~b, 1));
    }

    /**
     * 二进制乘法运算的本质是移位运算（x2等于向左移动一位）
     * @param a
     * @param b
     * @return
     */
    public int multiply(int a, int b) {
        int ans = 0;
        int p = 1;
        for (int i = 0; i < 32; i++) {
            if ((b & (p << i)) > 0) {
                ans = add(ans, a << i);
            }
        }
        return ans;
    }

    /**
     * 基础版，不支持负数
     * @param a
     * @param b
     * @return
     */
    public int div(int a, int b) {
        int ans = 0;
//        for (int i = 31; i >= 0 ; i--) {
        for (int i = 31; i >= 0 ; i = minus(i, 1)) {
            if ((a >> i) >= b) {
                ans |= (1 << i);
//                a -= (b << i);
                a = minus(a, b << i);
            }
        }
        return ans;
    }

    /**
     * 不支持最小负数，因为没有最小负数的正数
     * @param a
     * @param b
     * @return
     */
    public int div2(int a, int b) {
        int ans = 0;
        // 转正数
        int p = a < 0 ? -a : a;
        int q = b < 0 ? -b : b;

        for (int i = 31; i >= 0 ; i = minus(i, 1)) {
            if ((p >> i) >= q) {
                ans |= (1 << i);
                p = minus(p, q << i);
            }
        }
        // 结果正负判断
        return a < 0 ^ b < 0 ? -ans : ans;
    }

    /**
     * 支持最小负数时需要将最小负数增大
     * @param a
     * @param b
     * @return
     */
    public int div3(int a, int b) {
        if (a == 0) {
            return 0;
        }
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        }
        if (a != Integer.MIN_VALUE && b != Integer.MIN_VALUE) {
            return div2(a, b);
        }
        // a 或者 b = Integer.MIN_VALUE
        if (a != Integer.MIN_VALUE) {
            return 0;
        }
        if (b == -1) {
            return Integer.MAX_VALUE;
        }
        // a = Integer.MIN_VALUE
        // 增大a的值,对于b大于0来说结果值需要-1
        a += (b > 0) ? b : -b;
        return div2(a, b) + (b > 0 ? -1 : 1);
    }

    public static void main(String[] args) {
        Code_BitOperationAddMinusMultiplyDivide codeBitOperationAddMinusMultiplyDivide = new Code_BitOperationAddMinusMultiplyDivide();

        System.out.println("codeBitOperationAddMinusMultiplyDivide.add(1, 2) = " + codeBitOperationAddMinusMultiplyDivide.add(1, 2));
        System.out.println("codeBitOperationAddMinusMultiplyDivide.add(1, 2) = " + codeBitOperationAddMinusMultiplyDivide.add(512, 10));

        System.out.println("codeBitOperationAddMinusMultiplyDivide.minus(10, 11) = " + codeBitOperationAddMinusMultiplyDivide.minus(10, 11));
        System.out.println("codeBitOperationAddMinusMultiplyDivide.minus(10, 11) = " + codeBitOperationAddMinusMultiplyDivide.minus(20, 11));

        System.out.println("codeBitOperationAddMinusMultiplyDivide.multiply(2, 3) = " + codeBitOperationAddMinusMultiplyDivide.multiply(2, 3));
        System.out.println("codeBitOperationAddMinusMultiplyDivide.multiply(2, 3) = " + codeBitOperationAddMinusMultiplyDivide.multiply(221, 435));

        System.out.println("codeBitOperationAddMinusMultiplyDivide.div(10, 2) = " + codeBitOperationAddMinusMultiplyDivide.div(10, 2));
        System.out.println("codeBitOperationAddMinusMultiplyDivide.div(10, 3) = " + codeBitOperationAddMinusMultiplyDivide.div(10, 3));
        System.out.println("codeBitOperationAddMinusMultiplyDivide.div(-10, 3) = " + codeBitOperationAddMinusMultiplyDivide.div(-10, 3));

        System.out.println("codeBitOperationAddMinusMultiplyDivide.div2(-10, 3) = " + codeBitOperationAddMinusMultiplyDivide.div2(-10, 3));
        System.out.println("codeBitOperationAddMinusMultiplyDivide.div2(10, 3) = " + codeBitOperationAddMinusMultiplyDivide.div2(10, 3));

        System.out.println(Integer.MIN_VALUE / 3);
        System.out.println("codeBitOperationAddMinusMultiplyDivide.div3(Integer.MIN_VALUE, 3) = " + codeBitOperationAddMinusMultiplyDivide.div3(Integer.MIN_VALUE, 3));
    }

}
